package com.cn.algorithm02.class16;

/***
 * @author: hels
 * @description: 省份数量：https://leetcode.cn/problems/number-of-provinces/description/
 *
 **/
public class C02_UnionFindArray {

    public int findCircleNum(int[][] isConnected) {
        int N = isConnected.length;
        UnionFindArray unionFind = new UnionFindArray(N);
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                if (isConnected[i][j] == 1) {
                    unionFind.union(i,j);
                }
            }
        }
        return unionFind.sets();
    }

    public static class UnionFindArray {
//        父子节点关系数组
        private int[] parents;
//        代表节点大小
        private int[] size;
//        辅助数组，用于路径压缩
        private int[] help;
//        节点数量
        private int sets;

        public UnionFindArray(int N) {
            parents = new int[N];
            size = new int[N];
            help = new int[N];
            sets = N;
            for (int i = 0; i < N; i++) {
                parents[i] = i;
                size[i] = 1;
            }
        }

//        寻找i的祖宗，同时寻找过程做路径压缩
        public int findAncestor(int i) {
            int hi = 0;
            while (i != parents[i]) {
                help[hi++] = i;
                i = parents[i];
            }
//            路径压缩
            for (hi--; hi >= 0 ; hi--) {
                parents[help[hi]] = i;
            }
            return i;
        }

//        i j进行联合
        public  void union(int i, int j) {
            int fi = findAncestor(i);
            int fj = findAncestor(j);
            if (fi != fj) {
                if (size[fi] >= size[fj]) {
                    parents[fj] = fi;
                    size[fi] += size[fj];
                } else {
                    parents[fi] = fj;
                    size[fj] += size[fi];
                }
                sets--;
            }

        }

        public int sets() {
            return sets;
        }

    }


}
